#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <stdio.h>
#include <string.h>

using namespace std;


//sudoku
typedef pair<int, int> PII;

int rowHash[9];
int colHash[9];
int hash[9];

bool Valid(vector<vector<char> > &board)
{
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++){
            cout << board[i][j] << " ";
        }
        cout << endl;
    }

    int hash[9] = {0};
    for (int i = 0; i < 9; i++) {
        memset(hash, 0, sizeof(hash));
	for (int j = 0; j < 9; j++) {
	    if (board[i][j] == ' ') continue;
	    hash[board[i][j] - '1']++;
	    if (hash[board[i][j] - '1'] > 1) {cout << "Fail 1" << i << " " << j << " " << hash[board[i][j] - '1']<< endl; return false;}
	}
    }

    for (int j = 0; j < 9; j++) {
        memset(hash, 0, sizeof(hash));
	for (int i = 0; i < 9; i++) {
	    if (board[i][j] == ' ') continue;
	    hash[board[i][j] - '1']++;
	    if (hash[board[i][j] - '1'] > 1) {cout << "Fail 1" << i << " " <<j << " " << hash[board[i][j] - '1']<< endl; return false;}
	}
    }

    for (int i = 0; i < 3; i++) {
	for (int j = 0; j < 3; j++) {
	    memset(hash, 0, sizeof(hash));
	    for (int k = 0; k < 3; k++) {
		for (int l = 0; l < 3; l++) {
		    if (board[i*3+k][3*j+l] == ' ') continue;
		    hash[board[i*3+k][3*j+l]-'1']++;
		    if (hash[board[i*3+k][3*j+l]-'1'] > 1) {cout << "Fal 3" << i*3+k << " " << 3*j+l << " " <<  endl; return false;}
		} 
	    }
	}
    }
    cout << "---HK---return OK" << endl;
    return true;
}

PII findCell(vector<vector<char> > &board)
{
    for (int i = 0; i < 9; i++) {
	for (int j = 0; j < 9; j++) {
	    if (board[i][j] == ' ') return make_pair(i, j);
	}
    }
    return make_pair(-1, -1);
}

bool solveSudokuHelper(vector<vector<char> > &board) {
	    PII point = findCell(board);
	    if (point.first == -1) return true;
	    cout << endl << "Try point " << point.first << " " << point.second << endl;
	    for (int i = 1; i <= 9; i++) {
		board[point.first][point.second] = i+'0';
		if (Valid(board) && solveSudokuHelper(board)) return true;
		board[point.first][point.second] = ' ';
	    } 
    cout << "-------------------hk-----------------fail here-----" << endl;
    return false;
}

    void solveSudoku(vector<vector<char> > &board) {
	solveSudokuHelper(board);    
    }


vector<char> trans(const string &str)
{
    vector<char> ans;
    for (int i = 0; i < str.size(); i++) {
        ans.push_back(str[i]);
    }
    return ans;
}

//test in 1337 online judge and pass all the test
int main(int argc, char **argv)
{

    cout << "-----------------Test 1--------------------" << endl;
    vector<vector<char> > input(9);
    input[0] = trans("53  7    ");
    input[1] = trans("6  195   ");
    input[2] = trans(" 98    6 ");
    input[3] = trans("8   6   3");
    input[4] = trans("4  8 3  1");
    input[5] = trans("7   2   6");
    input[6] = trans(" 6    28 ");
    input[7] = trans("   419  5");
    input[8] = trans("    8  79");
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++){
            cout << input[i][j] << " ";
        }
        cout << endl;
    }
    cout << endl;
    solveSudoku(input);
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++){
            cout << input[i][j] << " ";
        }
        cout << endl;
    }
    cout << "-----------------Test 2--------------------" << endl;


    cout << "-----------------Test 3--------------------" << endl;


    cout << "-----------------Test 4--------------------" << endl;


    cout << "-----------------Test 5--------------------" << endl;

}
